package com.lsa.iview.chap2;

import java.util.HashSet;
import java.util.Set;

import org.apache.commons.lang.ObjectUtils;

import com.lsa.helpers.SingleLinkedList;
import com.lsa.helpers.SingleLinkedList.ListNode;

public class LinkedListQuestions {
	public static void removeDuplicatesWithStorage(SingleLinkedList<Integer> singleList) {
		Set<Integer> duplicates = new HashSet<Integer>();
		
		ListNode<Integer> head = singleList.getHead();
		
		ListNode<Integer> node = head;
		ListNode<Integer> prevNode = null;
		
		while(node != null) {
			if (!duplicates.add(node.data)) {
				singleList.remove(prevNode, node);
				node = prevNode;
			}
			prevNode = node;
			node = node.next;
		}
	}
	
	public static void removeDuplicatesNoStorage(SingleLinkedList<Integer> singleList) {
		ListNode<Integer> head = singleList.getHead();
		
		ListNode<Integer> node = head;
		
		while(node != null) {
			ListNode<Integer> testNode = node.next;
			ListNode<Integer> testPrevNode = node;
			
			while(testNode != null) {
				if (ObjectUtils.equals(testNode.data, node.data)) {
					singleList.remove(testPrevNode, testNode);
					testNode = testPrevNode;
				}
				
				testPrevNode = testNode;
				testNode = testNode.next;
			}
			
			node = node.next;
		}
	}
	
	public static ListNode<Integer> nthToTheLast(SingleLinkedList<Integer> singleList, int n) {
		ListNode<Integer> p2 = singleList.getHead();
		for (int i = 0; i < n; i++) {
			if (p2 == null) {
				return null;
			}
			p2 = p2.next;
		}
		if (p2 == null) {
			return null;
		}
		
		ListNode<Integer> p1 = singleList.getHead();
		while(p2.next != null) {
			p1 = p1.next;
			p2 = p2.next;
		}
		return p1;
	}
	
	public static SingleLinkedList<Integer> simulateAddition(SingleLinkedList<Integer> number1, SingleLinkedList<Integer> number2) {
		SingleLinkedList<Integer> result = new SingleLinkedList<Integer>();
		
		ListNode<Integer> node1 = number1.getHead();
		ListNode<Integer> node2 = number2.getHead();
		
		int carry = 0;
		
		while(node1 != null || node2 != null) {
			int n1 = node1 != null? node1.data : 0;
			int n2 = node2 != null? node2.data : 0;
			
			int r = n1 + n2 + carry;
						
			carry = r / 10;
			result.add(r % 10);
			
			if (node1 != null){
				node1 = node1.next;
			}
			
			if (node2 != null) {
				node2 = node2.next;
			}
		}
		
		if (carry > 0) {
			result.add(carry);
		}
		
		return result;
	}
	
	public static ListNode<Integer> nthToTheLastQuadratic(SingleLinkedList<Integer> singleList, int n) {
		int i = 0;
		ListNode<Integer> last = null;
		
		while( i <= n ) {
			ListNode<Integer> node = singleList.getHead();
			ListNode<Integer> prev = null;
			while(node != last) {
				prev = node;
				node = node.next;
			}
			
			i++;
			last = prev;
			
			if (last == null) {
				return null;
			}
		}
		
		return last;
	}
	
	public static ListNode<Integer> nthToTheLastRecursive(SingleLinkedList<Integer> singleList, int n) {
		ListNode<Integer> node = singleList.getHead();
		ListNode<Integer> last = null;
		while(node != null) {
			last = node;
			node = node.next;
		}
		
		return nthToTheLast(singleList.getHead(), last, n);
	}
	
	private static ListNode<Integer> nthToTheLast(ListNode<Integer> first, ListNode<Integer> last, int n) {
		if (last == null) {
			return null;
		}
		if (n == 0) {
			return last;
		}
		ListNode<Integer> prev = null; 
		ListNode<Integer> node = first;
		while(node != last) {
			prev = node;
			node = node.next;
		}
		return nthToTheLast(first, prev, n - 1);
	}
	
	public static ListNode<Integer> findCircle(SingleLinkedList<Integer> singleList) {
		ListNode<Integer> ptr1 = singleList.getHead();
		ListNode<Integer> ptr2 = ptr1;
		
		while(ptr1 != null && ptr2 != null) {
			ptr1 = ptr1.next;
			ptr2 = ptr2.next;
			if (ptr2 != null) {
				ptr2 = ptr2.next;
			}
			if (ptr2 == ptr1) {
				break;
			}
		}
		
		if (ptr2 == null) {
			return null;
		}
		
		ptr1 = singleList.getHead();
		while(ptr1 != ptr2) {
			ptr1 = ptr1.next;
			ptr2 = ptr2.next;
		}
		
		return ptr1;
	}
}
